Communication systems, particularly wireless communications and high-speed transmissions, often require the use of forward error correction algorithms to identify bit errors in received signals. Finite field arithmetic is highly useful in such forward error correction algorithms. Encryption algorithms also commonly use finite field arithmetic.
A finite field, commonly called a Galois field, is a field that contains only a finite number of numerical elements. One example of a Galois field is a set of five-digit binary numbers. There are a total of 32 such numbers and, for example, 31 of those numbers could constitute a Galois field. An important characteristic of a Galois field is that the arithmetic operators (addition, subtraction, multiplication, and division) are defined such that any arithmetic operation performed on elements of the field will always yield one of the elements in the field. In the binary example given, the addition and subtraction operations can be carried out as exclusive-OR (XOR) logic operations, and multiplication can be carried out as logical shifts, AND, and XOR operations. Note that in some cases, such operations will yield results that are not within the set of five-digit numbers. However, as applied within the Galois field, these arithmetic operations are defined using an irreducible generator polynomial which creates a modulo operation on the result, whereby the result remains within the Galois field (i.e., the result is one of the finite number of elements).
In the discipline of Galois field mathematics, addition, subtraction, and multiplication of field elements are well understood, and these operations can be mapped efficiently into hardware or software domains. However, dividing one field element by another in a Galois field does not map very efficiently into either of the hardware or software domains. The most accepted way of performing division is to multiply the dividend by the multiplicative inverse of the divisor, as follows:βi/βj=βi×βj−1  (1)where, βi, and βj are elements of the field. The multiplicative inverse of an element of a Galois field can be found either by using a ROM-based a look-up table (LUT) or by using a recursive circuit to implement Fermat's Little Theorem (Pierre de Fermat, first published in 1640). Using the look-up table approach, the function requires a fair amount of memory to implement, specifically 2m×m, where 2m=N+1, and N is the number of elements in the Galois field.
Fermat's Little Theorem states that, for any Galois field element β, the multiplicative inverse can be found by computing β−1=βN−2, where N is the total number of elements in the field. βN−2 can be found recursively via two methods:β−1=βN−2=β2×β4×β8× . . . ×β2m−1  (2)β−1=βN−2=(β× . . . (β×(β×β2)2)2 . . . )2  (3)where 2m=N+1. Using equation (2), the ability to efficiently raise a Galois field element to a power of 2m, i.e., 2, 4, 8, etc., is of critical importance. In equation (3), it is the ability to efficiently square a Galois field element that is the most critical item. For either recursive approach, the βm operation is performed via a recursive application of a squaring operation, which is accomplished by multiplying the field element by itself.
FIG. 1 illustrates a serial computation architecture 100 required to implement the approach of equation (2). In particular, a squaring operation 102 denoted by ( )2 is performed on the element β to produce β2. A second squaring operation 104 is performed on the output β2 of the first squaring operation 102 to produce β4. A first multiplication operation 106 is then performed on the outputs of the first and second squaring operations 102 and 104 (β2 and β4) to yield β6. A third squaring operation 108 is performed on the output β4 of the second squaring operation 104 to produce β8. A second multiplication operation 110 is then performed on the outputs of the first multiplication operation 106 (β6) and the third squaring operation 108 (β8) to yield β14. This process is repeated for m−2 stages until the output of the multiplier of the m−2th stage yields βN−2. For example, where m=5 and 2m=N+1=32, the circuit in FIG. 1 would include one additional stage with squaring operation 112 and multiplication operation 114 to yield an output value β30=β−1. Each of the squaring operations and multiplication operations can be carried out by performing an actual multiplication operation in hardware or software or by using a look-up table.
FIG. 2 illustrates the serial computation architecture 200 required to implement the approach of equation (3). In particular, a squaring operation 202 denoted by ( )2 is performed on the element β to produce β2. A second squaring operation 204 is performed on the output β2 of the first squaring operation 202 to produce β4. A first multiplication operation 206 is then performed on the outputs of the first and second squaring operations 202 and 204 (β2 and β4) to yield β6. A third squaring operation 208 is performed on the output β6 of the first multiplication operation 206 to produce β12. A second multiplication operation 210 is then performed on the output of the third squaring operation 208 (β12) and the output of the first squaring operation 202 (β2) to yield β14. This process is repeated for m−2 stages until the output of the m−2th stage yields βN−2. For example, where m=5 and 2m=N+1=32, the circuit in FIG. 2 would include one additional stage with squaring operation 212 and multiplication operation 214 to yield an output value β30=β−1.
The types of serial architecture shown in FIGS. 1 and 2 have long computation delays, decreasing the data throughput. Accordingly, there remains a need for an efficient approach to computing the multiplicative inverse of elements in a Galois field.